package com.dmall.play.interview.test;

import java.util.ArrayList;
import java.util.List;

public class Leetcode120V2 {

    public int minimumTotal(List<List<Integer>> triangle) {
        return backTrack(triangle, 0, 0);
    }

    private int backTrack(List<List<Integer>> triangle, int row, int col) {
        if (row == triangle.size()) {
            return 0;
        }

        int temp = triangle.get(row).get(col);
        int left = backTrack(triangle, row + 1, col);
        int right = backTrack(triangle, row + 1, col + 1);
        return Math.min(left, right) + temp;
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> item1 = new ArrayList<>();
        item1.add(2);
        List<Integer> item2 = new ArrayList<>();
        item2.add(3);
        item2.add(4);
        List<Integer> item3 = new ArrayList<>();
        item3.add(6);
        item3.add(5);
        item3.add(7);
        List<Integer> item4 = new ArrayList<>();
        item4.add(4);
        item4.add(1);
        item4.add(8);
        item4.add(3);
        triangle.add(item1);
        triangle.add(item2);
        triangle.add(item3);
        triangle.add(item4);

        Leetcode120V2 leetcode120 = new Leetcode120V2();
        System.out.println(leetcode120.minimumTotal(triangle));
    }
}
